# ----------
# User Instructions:
# 
# Define a function, search() that takes no input
# and returns a list
# in the form of [optimal path length, y, x]. For
# the grid shown below, your function should output
# [11, 4, 5].
#
# If there is no valid path from the start point
# to the goal, your function should return the string
# 'fail'
# ----------

# Grid format:
#   0 = Navigable space
#   1 = Occupied space

grid = [[0, 0, 1, 0, 0, 0],
        [0, 0, 1, 0, 0, 0],
        [0, 0, 1, 0, 1, 0],
        [0, 0, 1, 0, 1, 0],
        [0, 0, 1, 0, 1, 0]]

init = [0, 0]
goal = [len(grid)-1, len(grid[0])-1] # Make sure that the goal definition stays in the function.

delta = [[-1, 0 ], # go up
        [ 0, -1], # go left
        [ 1, 0 ], # go down
        [ 0, 1 ]] # go right

delta_name = ['^', '<', 'v', '>']

cost = 1

def search():
    open = [[0, init[0], init[1]]]
    maxy = len(grid) - 1
    maxx = len(grid[0]) - 1
    
    # create the visited matrix
    visited = []
    for i in range(maxy+1):
        row = []
        for j in range (maxx+1):
            row.append(0)
        visited.append(row)

    while (True):
        if (len(open)==0):
            return "fail"
        else:
            # Extract the node with the minimum g
            min = open[0]
            for i in range(1, len(open)):
                if (open[i][0] < min[0]):
                    min = open[i]
            open.remove(min)
            visited[min[1]][min[2]] = 1
            # Check if the node is the goal
            if (min[1:] == goal):
                return min
            # Expand the node
            for i in range(len(delta)):
                c = [min[0]+cost, min[1] + delta[i][0], min[2] + delta[i][1]]
                # ignore nodes outside the grid
                if (c[1] < 0 or c[1] > maxy): continue
                if (c[2] < 0 or c[2] > maxx): continue
                # ignore duplicates
                duplicate = False
                for j in range(len(open)):
                    if (c == open[j]): duplicate = True
                if (duplicate == True): continue
                # ignore walls
                if (grid[c[1]][c[2]] == 1): continue 
                # ignore already visited cells
                if (visited[c[1]][c[2]] == 1): continue 
                # add the candidate node to the list of open nodes
                open.append(c)              
        
print search()
raw_input()